Брезенхамов линијски алгоритам

Брезенхамов линијски алгоритам је алгоритам рачунарске графике који се користи за растеризацију линије тј. цртање линије у растерском облику. То подразумева да је за линију задату са две тачке почетном (x₀, y₀) и крајњом (x₁, y₁) потребно одредити скуп пиксела које треба обојити тако да тај скуп пиксела представља што бољу апрокцимацију линије.

Алгоритам је развио Џек Елтон Брезенхам 1962. у IBM-у. Био је то један од најранијих алгоритама рачунарске графике. Пошто је линија објекат од изузетног значаја за графику и често је потребно вршити исцртавање огромног броја линија алгоритам за циљ има ефикасност. Ефикасност се постиже коришћењем искључиво целобројне аритметике чије операције су знатно јефтиније од операција у покретном зарезу.

Једноставност и брзина алгоритма чине да је он и данас у широкој употреби. Једноставност алгоритма омогућава чак и хардверску имплементацију.

Алгоритам

Најпре ће бити описан основни алгоритам за цртање линија а затим постепено увођена побољшања која воде ка извођењу Брезенхамовог алгоритма.

Подразумева се да је линија задата са две тачке, почетном (x₀, y₀) и крајњом (x₁, y₁) и да важи x₀ < x₁. Такође, подразумева се да је потребно нацртати линију дебљине једног пиксела и да је функција за цртање пиксела дата. Алгоритам ће бити изложен само за линије првог квадранта за које важи: $0\leq m={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\leq 1$ тј. да им је коефициент правца већи од 0 а мањи или једнак 1. Овај простор ће бити називан првим октантом. Осталих седам случајева обрађује се симетрично.

Оно што треба нагласити је да је за линије за које важи $|m|\leq 1$ у свакој колони тј. за свако $x_{0}\leq x\leq x_{1}$ треба означити тачно један пиксел. За остале линије је потребно означити тачно један пиксел у врсти.

Алгоритам грубе силе

Алгоритам грубе силе за цртање линије заснива се на примени једначине праве. Једначина праве кроз две тачке је:

y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}.

За свако $x=x_{0},...,x_{1}$ рачунамо вредност $y$ и тада је потребно обојити пиксел $(x,\left\lfloor y+0.5\right\rfloor )$ .

Овај приступ није добар јер се вредност y увек изнова рачуна и због коришћења аритметичких операција у покретном зарезу.

Инкрементални алгоритам

Вредност y је могуће рачунати на основу претходно израчунатих вредности.

y_{i+1}=m*x_{i+1}+B

, где је B слободан члан

y_{i+1}=m*(x_{i}+1)+B

y_{i+1}=y_{i}+m

За свако $x=x_{0},...,x_{1}$ рачунамо вредност $y$ и тада је потребно обојити пиксел $(x,\left\lfloor y+0.5\right\rfloor )$ .

Овај приступ је добар јер елиминише множење и рачунање из почетка вредности за y. Међутим, опет је проблем рад са операцијама у покретном зарезу пошто је вредност m реална.

Брезенхамов алгоритам

Досадашње проблеме решава Брезенхамов алгоритам.

Пиксели се сада посматрају као чворови квадратне мреже.

Једначина праве у имплицитном облику, записана као функција од (x,y), је:

f(x,y)=0=Ax+By+C

, где су константе

A=\Delta y,B=-\Delta x,C=(\Delta x)b

За тачке на линији је f(x,y) = 0, за тачке испод линије је f(x,y) > 0, за тачке изнад линије је f(x,y) < 0.

Претпоставимо да смо досли до тачке i која се налази на линији. Пошто смо у овом тренутку ограничени на линије из првог октанка следећи пиксел који посматрамо ће имати x координату x_i+1. Пошто је коефицијент правца првог у првом октанту већи од 0 а мањи од 1 y координата следећег пиксела ће бити или y_i или y_i+1. Дакле, имамо две тачке које су кандидати за одабир и треба да одаберемо ону која најбоље апроксимира линију тј. ону која је најближа линији. Тачку са координатама (x_i+1, y_i) означаваћемо као тачку Е (east), а тачку са координатама (x_i+1, y_i+1) као тачку NE (northeast).

Коју од ове две тачке треба одабрати одређујемо коришћењем средишње тачке М (midpoint) која има координате (x_i+1, y_i+½). Ове координате уврштавамо у једначину праве:

d=f(x_{i}+1,y_{i}+{\frac {1}{2}})=Ax_{i}+A+By_{i}+{\frac {1}{2}}B+C

Ово је такозвана променљива одлучивања јер на основу њеног знака одређујемо који пиксел бирамо. Ако је вредност d мања од 0 значи да је тачка М изнад праве тј. да је права ближа тачки Е тако да у том случају бојимо пиксел Е. Ако је вредност d већа од нуле то значи да је тачка М испод праве тј. да је права ближа тачки NE и у том случају бојимо пиксел NE.

Вредност променљиве одлучивања може се рачунати инкрементално.

Ако је у претходном кораку одабрана тачка Е координате следеће средишње тачке су $M_{E}=(x_{i}+2,y_{i}+{\frac {1}{2}})$ и када се те координате уврсте у једначину праве добијамо нову вредност функције одлучивања:

d_{new}=f(x_{i}+2,y_{i}+{\frac {1}{2}})=(Ax_{i}+1)+A+By_{i}+{\frac {1}{2}}B+C

d_{new}=d_{old}+A=d_{old}+\Delta y

Ако је у претходном кораку одабрана тачка NЕ координате следеће средишње тачке су $M_{NE}=(x_{i}+2,y_{i}+{\frac {3}{2}})$ и када се те координате уврсте у једначину праве добијамо нову вредност функције одлучивања:

d_{new}=f(x_{i}+2,y_{i}+{\frac {3}{2}})=(Ax_{i}+1)+A+By_{i}+{\frac {3}{2}}B+C

d_{new}=d_{old}+A+B=d_{old}+\Delta y-\Delta x

Полазни пиксел је тачка (x₀, y₀) и он се свакако налази на линији. Почетна вредност променљиве одлучивања је:

d_{start}=f(x_{0}+1,y_{0}+{\frac {1}{2}})=Ax_{0}+A+By_{0}+{\frac {1}{2}}B+C=f(x_{0},y_{0})+A+{\frac {1}{2}}B=A+{\frac {1}{2}}B

Пошто желимо да радимо искључиво са целим бројевима а за одлучивање нам је битан само знак променљиве одлучивања ову вредност можемо помножити са 2 па добијамо: $d_{start}=2A+B$

Због тога се и све остале вредности множе са 2:

ако је одабрана тачка Е у претходном кораку $d_{new}=d_{old}+2\Delta y$
ако је одабрана тачка NЕ $d_{new}=d_{old}+2\Delta y-2\Delta x$

Овако је поново уведено множење, али пошто је ово множење са 2 оно може бити извршено као шифтовање улево за једну позицију тако да не утиче значајно на смањење ефикасности алгоритма. Овако добијамо алгоритам који користи искључиво сабирање, одузимање и шифтовање.

Имплементација

Приказана је имплементација у програмском језику C^[1]. У првом делу се уместо замена места координатама ради покривања свих осам случајева врши одређивање за које ће вредности бити мењане координате и иницијализација променљиве одлучивања.

void line(int x0, int y0, int x1, int y1) {
 
  int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;
  int dy = abs(y1-y0), sy = y0<y1 ? 1 : -1; 
  int err = (dx>dy ? dx : -dy) << 1, e2;
 
  for(;;){
    setPixel(x0,y0);
    if (x0==x1 && y0==y1) break;
    e2 = err;
    if (e2 >-dx) { err -= dy; x0 += sx; }
    if (e2 < dy) { err += dx; y0 += sy; }
  }
}

Види још

Сајрус-Беков алгоритам

Литература

Janičić, Predrag (2008). Rečunarska grafika (PDF). elektronsko izdanje.

Референце

^ [1]^{[мртва веза]}

[impl-1] [1]^{[мртва веза]}

[1]